Cellular Automata (CA)
2025-01-07
Consider cells on a two-dimensional regular grid. Each cell can be either 1 (alive) or 0 (dead). Based on an initial population, new generations are derived from the current state according to the following rules:
Example based on random initial state:
Result shows complex structures:
Stanislaw Ulam (1940s): modeling growth of chrystals on lattice networks
John von Neumann (1940s): work on self-replicating systems
John Horton Conways (1970s): Game of Life
Stephen Wolfram (1983): Fundamental theoretical work
Stephen Wolfram (2002): “A New Kind of Science”
Numerous practical applications evolved at the same time.
Cellular automata are suitable to model dynamic spatiotemporal processes / systems in:
A cellular automaton is a 4-tuple \((Z, S, N, f)\):
Space is partitioned into equal geometric objects:
At each point in time, the state of a cell is unique. The finite number of possible cell states cells are based on a set \(S\) containing numbers or letters from an alphabet \(A\): \(S = \{s | s \in A\}\)
A function \(C : Z \rightarrow S\) that assigns states to all cells is called configuration. The configuration at the simulation start is called initial configuration, start configuration, or sometimes initial conditions.
The state of a cell at time \(t\) depends on
\[f: Q^n \rightarrow Q\]
\(f\) might be
For the same initial conditions, deterministic automata always lead to the same simulation results. Stochastic automata include randomness in \(f\) and generally lead to different results for the same initial conditions.
A two-dimensional regular grid: \[Z = \{ (i,j) | i,j \in \mathbb{N} \land 0 \leq i < n \land 0 \leq j < m \}\]
Moore neighborhood: \[N_{i,j} = \{(k,l) \in Z : |x-x_0| \leq 1 \land |y-y_0| \leq 1 \}\]
State space (dead or alive): \[S = \{0,1\}\]
Transition function: \[ f_{i,j}(t+1) = \begin{cases} 1 & \textrm{for} ~ \sum_{(k,l) \in N_{i,j}} f_{k,l}(t) = 3 \\ 1 & \textrm{for} ~ \sum_{(k,l) \in N_{i,j}} f_{k,l}(t) = 2 \land f_{i,j}(t) = 1\\ 0 & \textrm{else} \end{cases} \]
Formally, cellular automata assume infinite grids but practical simulation requires finite grids. At the grid boundaries / corners, the neighbourhood is different and must be specified.
In one simulation step, the transition function is applied to all cells simultaneously (though usually implemented in a sequential for-loop style). To compute the next state of a cell \(z_{i,j}(t+1)\) we only use neighbours and the actual cell at time \(t\). This is called synchronous updating. In contrast, asynchronous updating also uses neighbours at time \(t+1\) if they have been already computed.
Synchronous updating: order of processing cells is NOT important.
Asynchronous updating: order of processing cells is influences results. All examples in this lecture are synchronous.
Wolfram distinguishes four different classes of (one-dimensional) CAs based on evolving patterns:
Examples (1d, \(t\) is on the y-axis -> each new line is a new time step)
(source: http://www.uni-forst.gwdg.de/~wkurth/fs08_v05.pdf)
Examples (1d, \(t\) is on the y-axis -> each new line is a new time step)
(source: http://www.uni-forst.gwdg.de/~wkurth/fs08_v05.pdf)
Modeling traffic:
Road (single-lane, 1d, circular) is divided into cells. Each cell is either empty or holds a single car.
Velocity of cars is an integer between 0 and 5.
Update rules:
Based on varying input parameters (lingering probability, maximum speed), it can be seen that traffic flow depending on traffic density has different optima. This model explains traffic jams as a result of overreactions and not complying with safety gaps.
Extensions:
Schelling (1971) presented a simple CA to explain social segregation:
Parameters:
Algorithm update:
Instead of continous diffusion models through partial differential equations, one can look at diffusion at the partcile level and use a one-dimensional CA:
We consider 5 genera of grasses (Lolium, Agrostis, Holcus, Poa, Cynosurus). Certain genera might displace others over time. We can model this competition as a two-dimensional stochastic CA with a von Neumann neighborhood (4 NBs):
| Lolium | Agrostis | Holcus | Poa | Cynosurus | |
|---|---|---|---|---|---|
| Lolium | 1 | 0.02 | 0.06 | 0.05 | 0.03 |
| Agrostis | 0.23 | 1 | 0.09 | 0.32 | 0.37 |
| Holcus | 0.06 | 0.08 | 1 | 0.16 | 0.09 |
| Poa | 0.44 | 0.06 | 0.06 | 1 | 0.11 |
| Cynosurus | 0.03 | 0.02 | 0.03 | 0.05 | 1 |
\(T\) is not symmetric, rows represent neighbours whereas columns represent a certain cell that may or may not be replaced.
Let \(z_{i,j}(t)\) denote a cell and let \(T(s,n)\) be a function that returns column \(s\) and row \(n\) of the replacement table \(T\). To derive the next state of a cell we perform the following operations:
\[ p = \frac{1}{4} \begin{pmatrix} T(z_{i,j}(t), z_{i-1,j}(t)) \\ T(z_{i,j}(t), z_{i,j-1}(t)) \\ T(z_{i,j}(t), z_{i+1,j}(t)) \\ T(z_{i,j}(t), z_{i,j+1}(t)) \end{pmatrix} \]
\(p_k\) is the probability that a cell is replalced by the \(k\)-th neighbor.
Draw a random number \(r \sim U(0,1)\) and create four nonintersecting intervals \((0,p_1],(p_1,p_1+p_2],(p_1+p_2,p_1+p_2+p_3],(p_1+p_2+p_3,p_1+p_2+p_3+4]\).
If \(r\) falls into one of these intervals, \(z_{i,j}(t)\) is replaced by the corresponding neighbor, otherwise it is not replaced.
Example: Cell \(z_{i,j}(t)\) is Agrostis, neighbors are (Holcus,Agrostis, Holcus, Lolium). The replacement table yields \[p = \frac{1}{4}(0.08, 1, 0.08, 0.06)^T = (0.02, 0.25, 0.02, 0.015)^T\] and the intervals are thus \((0,0.02], (0.02, 0.27], (0.27, 0.29], (0.29, 0.305]\).
Assuming e.g. \(r=0.28\), the cell would be replaced by Holcus.
The replacement table may come from lab experiments or empirical field studies.
Simulation results show that the Agrostis genus “wins”.
The (free) NetLogo software (https://ccl.northwestern.edu/netlogo) contains numerous cellular automata as well as many other agent-based models.